package com.ashin.dp;

import org.junit.Test;

/**
 * 最长公共子序列
 * 什么是子序列
 * abcdef
 * 其中ae为上面序列的子序列，相对位置不能变比如ea就不是上面序列的子序列
 * 而公共子序列距离如下，又两个序列如下
 * education
 * school
 * 公共子序列如下
 * co
 * 而最长公共子序列顾名思义
 *
 * @author Ashin
 */
public class LCS {


    @Test
    public void testA() {
        System.out.println((int) ('a'));
        System.out.println((int) ('A'));
        System.out.println((int) ('0'));
    }


    /**
     * 采用递归的形式，效率很差
     */
    @Test
    public void lcsRecursion() {
        String as = "abcadb";
        String bs = "xbcxxxdb";

        System.out.println(lcs(as.toCharArray(), bs.toCharArray()));
    }


    public String lcs(char[] a, char[] b) {
        if (a.length == 0 || b.length == 0) {
            return "";
        }
        if (a[a.length - 1] == b[b.length - 1]) {
            return lcs(new String(a).substring(0, a.length - 1).toCharArray(),
                    new String(b).substring(0, b.length - 1).toCharArray()
            ) + a[a.length - 1];
        } else {
            String r1 = lcs(a, new String(b).substring(0, b.length - 1).toCharArray());
            String r2 = lcs(new String(a).substring(0, a.length - 1).toCharArray(), b);

            return r1.length() > r2.length() ? r1 : r2;
        }
    }

    @Test
    public void lcsLongest() {
        String as = "program";
        String bs = "algorithm";

        System.out.println(lcsIterator(as.toCharArray(), bs.toCharArray()));
    }

    /**
     * 最长公共子序列
     *
     * @param a
     * @param b
     * @return
     */
    public int lcsIterator(char[] a, char[] b) {
        int[][] dp = new int[a.length + 1][b.length + 1];

        for (int rowIdx = 1; rowIdx <= a.length; rowIdx++) {
            for (int colIdx = 1; colIdx <= b.length; colIdx++) {
                if (a[rowIdx - 1] == b[colIdx - 1]) {
                    dp[rowIdx][colIdx] = Math.max(dp[rowIdx - 1][colIdx], dp[rowIdx][colIdx - 1]) + 1;

                } else {
                    dp[rowIdx][colIdx] = Math.max(dp[rowIdx - 1][colIdx], dp[rowIdx][colIdx - 1]);
                }
            }
        }

        return dp[a.length][b.length];
    }

    /**
     * 最长公共字串
     *
     * @param a
     * @param b
     * @return
     */
    public int lcssIterator(char[] a, char[] b) {
        int[][] dp = new int[a.length + 1][b.length + 1];

        int max = 0;
        for (int aIdx = 1; aIdx < a.length; aIdx++) {
            for (int bIdx = 1; bIdx < b.length; bIdx++) {
                if (a[aIdx - 1] == b[bIdx - 1]) {

                    dp[aIdx][bIdx] = dp[aIdx - 1][bIdx - 1] + 1;

                    max = Math.max(dp[aIdx][bIdx], max);
                } else {
                    dp[aIdx][bIdx] = 0;
                }

            }
        }

        return max;
    }


}
